/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr||p==nullptr||q==nullptr){
            return nullptr;
        }
        vector<TreeNode*> path1;
        GetNodePath(root,p,path1);
        
        vector<TreeNode*> path2;
        GetNodePath(root,q,path2);
        
        return GetLastCommonNode(path1,path2);
    }
    
    bool GetNodePath(TreeNode* root, TreeNode* node, vector<TreeNode*> & path){
        if(root==nullptr){
            return false;
        }
        path.push_back(root);
        if(root==node){
            return true;
        }
        bool found=GetNodePath(root->left,node,path);
        if(!found){
            found=GetNodePath(root->right,node,path);
        }
        if(!found){
            path.pop_back();
        }
        return found;
    }
    
    TreeNode* GetLastCommonNode(const vector<TreeNode*>& path1,const vector<TreeNode*>& path2){
        vector<TreeNode*>::const_iterator iterator1=path1.begin();
        vector<TreeNode*>::const_iterator iterator2=path2.begin();
        TreeNode* last=nullptr;
        while(iterator1!=path1.end()&&iterator2!=path2.end()){
            if(*iterator1==*iterator2){
                last=*iterator1;
            }
            iterator1++;
            iterator2++;
        }
        return last;
    }
};